import collections


class Solution(object):
    def smallestSufficientTeam(self, req_skills, people):
        n = len(req_skills)
        d = {skill: index for index, skill in enumerate(req_skills)}
        st = {0: []}
        for id, p in enumerate(people):
            now = 0
            for skill in p:
                if skill in d:
                    now |= (1 << d[skill])
            if now > 0:
                next_st = {}
                for node in st:
                    if node in next_st:
                        if len(st[node]) < len(next_st[node]):
                            next_st[node] = st[node]
                    else:
                        next_st[node] = st[node]
                    next_val = node | now
                    if next_val in next_st:
                        if len(st[node]) + 1 < len(next_st[next_val]):
                            next_st[next_val] = st[node] + [id]
                    else:
                        next_st[next_val] = st[node] + [id]
                st = next_st
        ans = float('inf')
        out = []
        for val in st:
            if val == (2 ** n - 1):
                if len(st[val]) < ans:
                    out = st[val]
        return out


data = Solution()
req_skills = ["java", "nodejs", "reactjs"]
people = [["java"], ["nodejs"], ["nodejs", "reactjs"]]
print(data.smallestSufficientTeam(req_skills, people))
